package advance.day03;


import java.util.Arrays;

/**
 * 描述：
 *      求出元素总和最大的子矩阵
 * @author hl
 * @version 1.0
 * @date 2020/11/6 10:23
 */
public class MaximalRectangle2 {
    public static void main(String[] args) {
        int[][] map = { { 1, 0, 5, 1 },{ 1, -9, 1, 8 },{ 1, 1, 1, 0 }};
        System.out.println(Arrays.toString(getMaxMatrix(map)));
    }

    /**
     *
     * @param matrix
     * @return  返回矩阵左上角和右下角的坐标
     */
    public static int[] getMaxMatrix(int[][] matrix) {
        int[] ans = new int[4];//保存答案
        int m = matrix.length;
        int n = matrix[0].length;
        int[] b = new int[matrix[0].length];//在指定行范围内的该列上的数的总和
        int lr = 0, lc = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            Arrays.fill(b,0);
            for (int j = i; j < m; j++) {
                int sum = 0;//每一行从0开始dp，保存该行上的每个位置最大值
                for (int k = 0; k < n; k++) {
                    b[k] += matrix[j][k];
                    if (sum > 0) {
                        sum += b[k];
                    }else{//sum < 0，b[k]为最大的值
                        sum = b[k];
                        lr = i;
                        lc = k;//从第i行开始， k - 1 列不能形成最大值
                    }
                    if (sum > maxSum) {
                        maxSum = sum;
                        ans[0] = lr;
                        ans[1] = lc;
                        ans[2] = j;
                        ans[3] = k;
                    }
                }
            }
        }
        return ans;
    }
}
